For the High Efficiency Video Coding (HEVC) standard currently under development as H.264/MPEG-4 AVC, the application of TUs to residual blocks is represented by a tree as described in “Video Compression Using Nested Quadtree Structures, Leaf Merging, and Improved Techniques for Motion Representation and Entropy Coding,” IEEE Transactions on Circuits and Systems for Video Technology vol. 20, no 12, pp. 1676-1687, December 2010.
Coding Layers
The hierarchical coding layers defined in the standard include video sequence, picture, slice, and treeblock layers. Higher layers contain lower layers.
Treeblock
According to the proposed standard, a picture is partitioned into slices, and each slice is partitioned into a sequence of treeblocks (TBs) ordered consecutively in a raster scan. Pictures and TBs are broadly analogous to frames and macroblocks, respectively, in previous video coding standards, such as H.264/AVC. The maximum allowed size of the TB is 64×64 pixels luma (intensity), and chroma (color) samples).
Coding Unit
A Coding Unit: (CU) is the basic unit of splitting used for Intra and Inter prediction. Intra prediction operates in the spatial domain of a single picture, while Inter prediction operates in the temporal domain among the picture to be predicted and a set of previously-decoded pictures. The CU is always square, and can be 128×128 (LCU), 64×64, 3.2×32, 16×16 and 8×8 pixels. The CU allows recursive splitting into four equally sized blocks, starting from the TB. This process gives a content-adaptive coding tree structure comprised of CU blocks that can be as large as the TB, or as small as 8×8 pixels.
Prediction Unit (PU)
A Prediction Unit (PU) is the basic unit used for carrying the information (data) related to the prediction processes. In general the PU is not restricted to being square in shape, in order to facilitate partitioning, which matches, for example, the boundaries of real objects in the picture. Each CU may contain one or more PUs.
Transform Unit (TU)
As shown in FIG. 1, a root node 101 of the transform tree 100 corresponds to an N×N TU or “Transform Unit” (TU) applied to a block of data 110. The TU is the basic unit used for the transformation and quantization processes. In the proposed standard, the TU is always square and can take a size from 4×4 to 32×32 pixels. The TU cannot be larger than the PU and does not exceed the size of the CU. Multiple TUs can be arranged in a tree structure, henceforth—transform free. Each CU may contain one or more TUs, where multiple TUs can be arranged in a tree structure.
The example transform tree is a quadtree three with four levels 0-3. If the transform tree is split once, then four N/2×N/2 TUs are applied. Each of these TUs can subsequently be split down to a predefined limit. For Intra-coded pictures, transform trees are applied over “Prediction Units” (PUs) of Intra-prediction residual data. These PUs are currently defined as squares or rectangles of size 2N×2N, 2N×N, N×2N, or N×N pixels. For Intra-coded pictures, the square TU must be contained entirely within a PU, so the largest allowed TU size is typically 2N×2N or N×N pixels. The relation between a-j TUs and a-j PUs within this transform tree structure is shown in FIG. 1.
As shown in FIG. 2, a new PU structures has been proposed for the proposed HEVC standard as described by Cao, et al. “CE6.b1 Report on Short Distance Intra Prediction Method (SDIP),” JCTVC-E278, March 2011. With the SDIP method, PUs can be strips or rectangles 201 as small as one or two pixels wide, e.g. N×2, 2×N, N×1, or 1×N pixels. When overlaying a transform tree on an Intra-coded block, that has been partitioned into such narrow PUs, the transform tree is split to a level where the size of the TU is only 2×2 or 1×1. The TU size cannot be greater than the PU size; otherwise, the transformation and prediction process is complicated. The prior art SDIP method that utilizes these new PU structures define, for example, as 1×N and 2×N TUs. Due to the rectangular TU sizes, the prior art is not compatible with the transform tree structure that is in the current draft specification of the HEVC standard. The SDIP does not use the transform tree mandated in the standard, instead the TU size is implicitly dictated by the sizes of the PUs.
Hence, there is a need for a method of splitting and applying square and rectangular TUs on rectangular, and sometimes very narrow rectangular PUs, while still maintaining the tree structure of the TUs as defined by the proposed standard.